Techniques for realizing a pseudo-random function by using a one-directional function are known (refer to, e.g., Non-Patent Document 5). However, a pseudo-random function f realized by such a technique cannot efficiently give a zero knowledge proof of knowledge of x that satisfies y=f(x). A technique for efficiently giving a zero knowledge proof of knowledge of x that satisfies y=f(x) can be used to efficiently realize various cryptographic protocols. Therefore, there is a demand for efficient pseudo-random functions.
Meanwhile, many applications such as electronic voting, electronic money, electronic coupons and limited number of times of viewing/listening need to be used by anonymous users in order to protect the privacy of users. At the same time, the number of times for which a user can use such an application needs to be limited.
Number-limited anonymous authentication systems (refer to, e.g., Non-Patent Document 4) are systems suitable for realizing such applications. As a user utilizes such an application, the application provider (AP) authenticates the user by means of such a system so that the application provider provides the application to the user if the user is an honest user who observes the limit of number of times, where as the user can be identified if the user is not honest.
Particularly, the Non-Patent Document 4 proposes a scheme for counting the number of times of authentication of an anonymous user and realizes a number-limited anonymous authentication system by combining a member adding procedure using an ACJT group signature scheme (refer to, e.g., Non-Patent Document 1) and a tag mechanism.
However, the tag mechanism employed in the above-described number-limited anonymous authentication system is poorly efficient and, at the time of authentication, both the AP and the user have to calculate the modular exponentiation of the number of times proportional to the limited number of times k. For example, in the case of an electronic coupon or limited number of times of viewing/listening, the limited number of times may often exceed 10. Thus, the system of the above-cited Non-Patent Document 4 is poorly efficient if employed in such applications.    Non-Patent Document 1: G. Ateniese, J. Camenisch, M. Joye and G. Tsudik, “A Practical and Provably Secure Coalition—Resistant Group Signature Scheme”, In Advances in Cryptology—CRYPTO 2000, vol. 1880 of LNCS, pp. 255-270, Springer-Verlag, 2000    Non-Patent Document 2: P. S. L. M. Barreto, H. Y. Kim, B. Lynn, M. Scott, “Efficient Algorithms for Pairing-Based Cryptosystems”, In Advances in Cryptology—Crypto '2002, vol. 2442 of LNCS, pp. 354-368, Springer-Verlag, 2002    Non-Patent Document 3: Rafael Pass, “On Deniability in the Common Reference String and Random Oracle Model”, In Advances in Cryptology—CRYPTO 2003, vol. 2729 of LNCS, pp. 316-337, Springer-Verlag, 2003    Non-Patent Document 4: Isamu Teranishi, Jun Furukawa and Kazue Sako, “k-Times Anonymous Authentication (Extended Abstract)”, In Advances in Cryptology—ASIACRYPT 2004, vol. 3329 of LNCS, pp. 308-322, Springer-Verlag, 2004    Non-Patent Document 5: Oded Goldreich, “Foundation of Cryptography, Basic Tools”, Cambridge University Press, ISBN 0-521-79172-3, USA, 2001. pp. 148-169